알고리즘#include <algorithm>
#include <numeric>
범용 STL 알고리즘은 <algorithm> 헤더 파일에 정의되어 있다.
(numeric 헤더는 숫자 처리를 위한 알고리즘 정의)
시퀀스를 수정하지 않는 연산 find
find는 검색 공간의 오른쪽 개구간과 해당 구간에서 검색할 값을 정의하는 두 반복자를 인수로 취한다.
참조된 각 항목의 값을 비교하며, 값과 일치하는 항목을 발견하면, 값을 가르키는 반복자를 반환한다.
(시퀀스에 값이 포함되지 않은 경우, last와 동일한 반복자를 반환)
template <typename InputIterator, typename T>
InputIterator find(InputIterator first, InputIterator last, const T& value){
while(first!=last&&*first!=value) ++first;
return first;
}
실제 find 템플릿 함수는 위의 기본적인 동작과 특별한 반복자를 위한 특수화된 오버로드가 추가되어 있다.
vector<int> seq={3, 4, 7, 9, 2, 5, 7, 8};
auto it=find(seq.begin(), seq.end(), 7);
auto end=find(it+1, seq.end(), 7);
for(auto past=end+1; it!=past; ++it){
cout<<*it<<' ';
}
cout<<'\n';
STL은 항상 오른쪽 개구간으로 동작 ( , ]
위의 코드는 vector내의 7값이 항상 2번 존재함에 의존한다.
견고하게 만들기 위해 7이 없거나 한 개만 있을 경우 사용자 정의 예외를 정의하는 것이 좋다
if(it==seq.end()) throw no_seven{};
if(end==seq.end()) throw one_seven{};
또한 위의 코드에서 it+1과 같은 연산은 반복자가 임의 접근 반복자(ex 배열, vector, deque)인 경우만 동작한다.
list와 같은 컨테이너에서 사용할 수 있게 하기 위해서 반복자 하나를 복사한 뒤 증가 연산자를 사용할 경우,
list에서도 동작하게 할 수 있다.
위의 코드는 RandomAccessIterator만 사용 가능
아래와 같은 코드는 ForwardIterator에서도 구동한다.
list<int> seq={3, 4, 7, 9, 2, 5, 7, 8};
auto it=find(seq.begin(), seq.end(), 7), it2=it;
++it2;
auto end=find(it2, seq.end(), 7);
++end;
for(; it!=end; ++it){
cout<<*it<<' ';
}
더욱 확장해서 C++에서 기본 배열은 begin, end 메서드를 제공하지 않는다.
C++11에서는 배열과 모든 STL 컨테이너에서 사용할 수 있는 제네릭한 begin(), end() 자유함수를 제공한다.
#include <iostream>
#include <list>
#include <algorithm>
#include <sstream>
struct value_not_found{};
struct value_found_twice{};
template <typename Range, typename Value>
void print_interval(const Range& r, const Value& v, std::ostream& os=std::cout){
using std::begin; using std::end;
auto it=std::find(begin(r), end(r), v), it2=it;
if(it==end(r)) throw value_not_found();
++it2;
auto past=std::find(it2, end(r), v);
if(past==end(r)) throw value_found_twice();
++past;
for(; it!=past; ++it) os<<*it<<' ';
os<<'\n';
}
int main(void){
std::list<int> seq={3, 4, 7, 9, 2, 5, 7, 8};
print_interval(seq, 7);
int array[]={3, 4, 7, 9, 2, 5, 7, 8};
std::stringstream ss;
print_interval(array, 7, ss);
std::cout<<ss.str();
}
find_iffind_if는 특정 조건에 해당하는 첫 번째 항목을 검색해서 find를 일반화한다.
단일 값을 비교하는 대신, bool값을 반환하는 함수인 술어(Predicate)를 계산한다.
bool check(int i){ return i>4 && i<7; }
int main(void){
list<int> seq={3, 4, 7, 9, 2, 6, 7, 8};
auto it=find_if(begin(seq), end(seq), check);
cout<<"The first value in range is "<<*it<<'\n';
}
find_if 함수에 직접 람다식을 사용할 수도 있다.
auto it=find_if(begin(seq), end(seq), [](int i){ return i>4 && i<7; });
for_eachfor_each는 시퀀스의 각 요소에 함수를 적용하는데 사용한다.
C++03에서는 함수 개체를 미리 정의하거나 펑터 또는 의사 람다(psedo-lambda)를 작성해야 했다.
하지만, 범위 기반의 for 문이 보다 간결하기 때문에 반복문을 다시 구현하는 것이 더 간단하다.
시퀀스를 수정하는 연산 copy
copy 함수는 수정된 시퀀스가 일반적으로 시작 반복자를 통해서만 매개변수화 된다.
(오버플로로 오류가 발생하지 않도록 신중하게 써야함)
vector<int> seq={3, 4, 7, 9, 2, 5, 7, 8}, v;
r.resize(seq.size());
copy(seq.begin(), seq.end(), v.begin());
위처럼 사용하기 전에 v의 크기를 원본의 크기 또는 그 이사으로 확보해야 함
copy의 세 번째 인수로 ostream_iterator를 사용해서 해당 시퀀스를 출력하도록 할 수 있다.
copy(seq.begin(), seq.end(), ostream_iterator<int>(cout, ", "));
ostream_iterator는 출력 스트림을 위한 최소한의 반복자 인터페이스를 구축한다.
값을 할당하면, 구분자와 함께 참조된 출력 스트림으로 보낸다.
uniqueunique 함수는 시퀀스의 중복된 항목을 제거한다.
(시퀀스가 정렬되어 있어야 함)
unique는 고유한 값이 맨 앞에 정렬되고 중복된 값이 맨 끝에 항목에 재배치한다.
이 후 첫 번째 중복된 항목을 가르키는 반복자를 반환한다.
std::vector<int> seq={3, 4, 7, 9, 2, 5, 7, 8, 3, 4, 3, 9};
sort(seq.begin(), seq.end());
auto it=unique(seq.begin(), seq.end());
seq.resize(distance(seq.begin(), it));
중복값 제거 연산을 시퀀스/범위로 매개변수화된 제네릭 함수로 캡슐화
template <typename Seq>
void make_unique_sequence(Seq& seq){
using std::begin; using std::endl; using std::distance;
std::sort(begin(seq), end(seq));
auto it=std::unique(begin(seq), end(seq));
seq.resize(distance(begin(seq), it));
}
정렬 연산표준 라이브러리 정렬 함수는 매우 유연하고 강력하게 구현되어 있다.(거의 모든 상황에서 사용가능)
퀵 정렬을 기반으로 한 기반으로 한 이전의 구현은 평균 시간 복잡도가 O(nlog n)이지만, 최악의 경우
시간복잡도는 O(n^2)가 되었다. 최근 버전에서는 최악의 경우에서도 시간 복잡도가 O(n logn)인 intro-sort
를 기반으로 구현되어 있다.
intro-sort: 퀵 정렬, 힙 정렬을 결합한 하이브리드 정렬 알고리
즘
sort는 기본적으로 < 연산자를 사용한다.
시퀀스를 내림차순으로 정렬하는 것처럼 사용자 정의 비교 함수도 사용할 수 있다.
vector<int> seq={3, 4, 7, 9, 2, 5, 7, 8, 3, 4, 3, 9};
sort(seq.begin(), seq.end(), [](int x, int y){ return x>y; })
using cf=complex<float>;
vector<cf> v={{3, 4}, {7, 9}, {2, 5}, {7, 8}};
sort(v.begin(), v.end(), [](cf x, cf y){ return abs(x)<abs(y); });
auto lex=[](cf x, cf y){ return real(x)<real(y) || real(x)==real(y) && imag(x)<imag(y); };
sort(v.begin(), v.end(), lex);
수치 연산#include <numeric>
STL의 수치 연산은 <numeric> 헤더/라이브러리에 정의되어 있다.
iotaiota는 모든 항목에 지정한 값을 기준으로 1씩 증가하는 값을 연속적으로 채운 시퀀스를 생성한다.
accumulate
accumulate는 기본적으로 시퀀스의 합을 계산하고 사용자가 이진 함수를 제공할 경우,
임의의 동작을 수행한다.
inner_product
inner_product는 기본적으로 내적(dot product)를 수행하며 일반적인 형태로 각각 덧셈 및 곱셈을 대체하는
이진함수 개체를 지정할 수 있다.
partial_sum & adjacent_difference
vector<float> v={3.1, 4.2, 7, 9.3, 2, 5, 7, 8, 3, 4}, w(10), x(10), y(10);
iota(w.begin(), w.end(), 12.1);
partial_sum(v.begin(), v.end(), x.begin());
adjacent_difference(v.begin(), v.end(), y.begin());
float alpha=inner_product(w.begin(), w.end(), v.begin(), 0.0f);
float sum_w=accumulate(w.begin(), w.end(), 0.0f);
float product_w=accumulate(w.begin(), w.end(), 1.0f, [](float x, float y){ return x*y; });
STL 복잡도
| STL
알고리즘 복잡도 |
| O(1) |
swap, iter_swap |
| O(log n) |
lower_bound, upper_bound, equal_range, binary_search, push_heap, pop_heap |
| O(n log n) |
inplace_merge, stable_partition, 모든 정렬 알고리즘 |
| O(n^2) |
find_end, find_first_of, search, search_n |
| O(n) |
그 외 모든 알고리즘 |
반복자 문제점
반복자는 C++ 사용하는 컨테이너에서 매우 중요하게 사용된다.
하지만, 반복자는 매우 위험하고 인터페이스도 좋지 못하다.
반복자는 쌍으로 생성되어,
오직 프로그래머만이 종료조건으로 사용한 두 개의 반복자가 실제로 연관되어 있다고 보장할 수 있다.
- 끝을 가르키는 반복자(end)가 먼저 나오는 경우
- 다른 컨테이너에서 가져온 반복자
- 반복자가 더 큰 반복 단계를 만들어 끝을 가르키는 반복자를 방문하지 않음
반복자는 위와 같은 상황에 처해도 임의의 메모리에서 반복을 수행할 수 있으며,
프로그램이 접근 가능한 주소 공간을 벗어나지 않으면, 무한 루프에 빠지게 된다.
따라서 잘못 사용된 반복자가 다른 데이터를 손상시키기 전에 크래시를 발생시키는 것이 좋다
많은 STL 컨테이너들은 한 컨테이너에 대해서는 한 쌍(begin, end)쌍의 반복자를 인자로 받지만,
다른 컨테이너에 대해서는 시작 반복자(begin)만 가져와 사용한다.
copy(v.begin(), v.end(), w.begin());
따라서 위와 같은 경우, 복사 대상이 충분한 공간을 제공하는지, 임의의 메모리를 덮어 쓸수 있는지 사전에 검사할 수 없다.
x=inner_product(v.begin(), v.end(), w.begin());
x=dot(v, w);
두 번째 코드에서는 컨테이너 객체를 받기 때문에 내부적으로 동일한 크기의 벡터인지 검사가 가능하다.
C++17부터 범위(Range)가 도입되었다.(표준에서는 제외)
(범위는 begin, end를 반환하는 모든 타입)
범위를 사용하면, 하위 컨테이너, 컨테이너의 여감색 또는 일부 변형된 뷰도 나타낼 수 있으며,
함수 인터페이스를 다듬어서 크기 검사를 내부적으로 수행하게 구현할 수 있다.
반복자 기반 함수에 경우, 사용자 중심 인터페이스를 제공하는 것이 좋음